package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: lynn
 * @Descript:丑数
 * 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。
 * 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * @date: 2021/3/15 20:31
 * @version: 1.0
 */
public class Q33_GetUglyNumber {

    public static void main(String[] args) {
        int index=1500; //1500 -->859963392 ,5-->8
        System.out.println(doget(index));
    }
    //首先除2，直到不能整除为止，然后除5到不能整除为止，
    // 然后除3直到不能整除为止。最终判断剩余的数字是否为1，
    // 如果是1则为丑数，否则不是丑数。
    private static int doget(int index){
        if (index<0) throw new IllegalArgumentException("输入参数非法!");
        if (index==0) return 1;

        int[] arr=new int[index];
        arr[0]=1;
        int index2=0,index3=0,index5=0;
        for (int i = 1; i < index; i++) {
            arr[i]=Min(arr[index2]*2,arr[index3]*3,arr[index5]*5);
            index2=(arr[index2]*2<=arr[i])?++index2:index2;
            index3=(arr[index3]*3<=arr[i])?++index3:index3; //是 ++index2 ，不是 index2++
            index5=(arr[index5]*5<=arr[i])?++index5:index5;
        }
        return arr[index-1];
    }

    private static int Min(int n1, int n2, int n3)
    {
        int mid = n1 > n2 ? n2 : n1;
        return mid > n3 ? n3 : mid;
    }
}
